
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1395. -- [Baltic2005]Trip -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1395: [Baltic2005]Trip</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>28&nbsp;&nbsp;<span class=green>Solved: </span>7<br>[<a href='submitpage.php?id=1395'>Submit</a>][<a href='problemstatus.php?id=1395'>Status</a>][<a href='bbs.php?id=1395'>Discuss</a>]</center><h2>Description</h2><div class=content>这里有 N 座城镇, 和城镇之间的 M 巴士单行线(没有中间停靠站)。 城镇从1到N 标号。 一个旅行者在 0时刻位于 1号城镇想要到达 P 号城镇。他将乘坐巴士在T 时刻到达P 号城镇。如果他早到了，他必须等待。

对于任意一个巴士路线i, 我们知道其中的起点城镇si 和目标城镇ti 。我们也同样知道路线的出发时间和到达时间,但仅仅是近似值：我们知道巴士离开起点城镇si 在时间范围[ai, bi]内，且到达目标城镇ti 在时间范围[ci, di]内(端点值包括在内)。

旅行者不喜欢等待, 因此他要寻找一个旅行计划使得最大等待时间尽量小，同时保证绝对不会错过计划中的任何一辆巴士(意思是, 每次他换乘巴士, 他需要下车的巴士的最晚到达时间不会迟于他需要搭乘的下一辆巴士的最早出发时间)。

当计算等待时间时，我们必须假设最早可能到达的时间和最晚可能出发的时间。

编写一个程序，寻找一个最为合理的搭车计划。

</div><h2>Input</h2><div class=content>The first line contains the integer numbers N (1<=N<=50,000), M (1<=M<=100,000), P ( 1<= P<= N), and T (0<=T<=1,000,000,000).

The following M lines describe the bus routes. Each line contains the integer numbers si, ti, ai, bi, ci, di, where si and ti are the source and destination towns of the bus route i, and ai, bi, ci, di describe the departure and arrival times as explained above (1 <= si<=N, 1 <=ti<=N, 0<=ai<= bi < ci<=di<=1,000,000,000).

</div><h2>Output</h2><div class=content>只需要包含一个数——最合理搭车方案的最长可能等待时间。如果不可能保证在T 时刻到达城市P，那么输出-1。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 6 2 100<br />
1 3 10 20 30 40<br />
3 2 32 35 95 95<br />
1 1 1 1 7 8<br />
1 3 8 8 9 9<br />
2 2 98 98 99 99<br />
1 2 0 0 99 101<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>32</span></div><h2>HINT</h2>
			<div class=content><p>The most pessimistic case for the optimal travel plan for the above example is as follows:<br />
Time	Action<br />
0…1	Wait in town 1<br />
1…7	Take the bus line 3 from town 1 to town 1<br />
7…8	Wait in town 1<br />
8…9	Take the bus line 4 from town 1 to town 3<br />
9…35	Wait in town 3<br />
35…95	Take the bus line 2 from town 3 to town 2<br />
95…98	Wait in town 2<br />
98…99	Take the bus line 5 from town 2 to town 2<br />
99…100	Wait in town 2<br />
Total waiting time: 1+1+26+3+1=32<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1395'>Submit</a>][<a href='problemstatus.php?id=1395'>Status</a>][<a href='bbs.php?id=1395'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
